import java.util.*;

/**
 * @作者 钟先崟
 * @时间 2023-03-08 18:22
 * @说明
 */
public class Solution {
    public static void main(String[] args) {
//        letterCombinations("23").stream().forEach((String s) -> {
//            System.out.print(s + " ");
//        });

        letterCombinations("").stream().forEach((String s) -> {
            System.out.print(s + " ");
        });
    }

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了19.15%的用户
     * 内存消耗：40.2 MB, 在所有 Java 提交中击败了49.11%的用户
     *
     * @param digits
     * @return
     */
    public static List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();  //使用一个集合来存储所有的字母组合结果
        if (digits == null || digits.length() == 0) return combinations;

        //将号码字母对应关系存储进Map
        HashMap<Character, String[]> map = new HashMap<Character, String[]>() {{    //存储为数组更好操作
            put('2', new String[]{"a", "b", "c"});
            put('3', new String[]{"d", "e", "f"});
            put('4', new String[]{"g", "h", "i"});
            put('5', new String[]{"j", "k", "l"});
            put('6', new String[]{"m", "n", "o"});
            put('7', new String[]{"p", "q", "r", "s"});
            put('8', new String[]{"t", "u", "v"});
            put('9', new String[]{"w", "x", "y", "z"});
        }};

        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < digits.length(); i++) {
            String[] strings = map.get(digits.charAt(i));
            if (queue.size() == 0) {
                for (int j = 0; j < strings.length; j++) {
                    queue.add(strings[j]);
                }
            } else {
                int n = queue.size();
                for (int j = 0; j < n; j++) {
                    String poll = queue.poll();
                    for (int k = 0; k < strings.length; k++) {
                        queue.add(poll + strings[k]);
                    }
                }
            }
        }
        queue.forEach((String sb) -> {
            combinations.add(sb);
        });
        return combinations;
    }
}
